#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 200. 岛屿数量.py
@time: 2022/1/10 15:36
@desc: https://leetcode-cn.com/problems/number-of-islands/
@解题思路：
    1. dfs, Ot(mn), Os(mn)
    2. bfs, 思路：循环遍历grid数组，当其为1时候，岛屿数量加1，并将其本身与附近为1的元素都标0
    3. 并查集，Ot(MN)有个什么反阿克曼函数，忽略了，可以认为是常数, Os(MN)
'''
class DFSSolution(object):
    def dfs(self, grid, r, c):
        grid[r][c]=0
        # dfs其身边的元素
        nr, nc = len(grid), len(grid[0])
        for x, y in [(r-1, c), (r+1, c), (r, c-1), (r, c+1)]:
            if 0<=x<nr and 0<=y<nc and grid[x][y]=="1":
                self.dfs(grid, x, y)

    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        # 思路：循环遍历grid数组，当其为1时候，岛屿数量加1，并将其本身与附近为1的元素都标0
        nr = len(grid)
        if nr==0: return 0
        nc = len(grid[0])

        count = 0
        for r in range(nr):
            for c in range(nc):
                if grid[r][c]=="1":
                    count += 1
                    self.dfs(grid, r, c)
        return count

class BFSSolution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        nr = len(grid)
        if nr==0: return 0
        nc = len(grid[0])

        count = 0
        for r in range(nr):
            for c in range(nc):
                if grid[r][c]=="1":
                    count += 1
                    grid[r][c] = "0"
                    neighbors = [[r, c]]
                    while neighbors:
                        row, col = neighbors.pop(0)
                        for x, y in [(row-1, col), (row+1, col), (row, col-1), (row, col+1)]:
                            if 0<=x<nr and 0<=y<nc and grid[x][y]=='1':
                                grid[x][y] = '0'
                                neighbors.append([x, y])
        return count

class UnionFind:
    def __init__(self, n):
        # 连通数量的个数
        self.count = n
        self.parent = [0] * n
        for i in range(n): self.parent[i] = i

    def find(self, x):
        while not x == self.parent[x]:
            # 压缩
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        # 已经是同一个连通分量就跳过
        if xRoot == yRoot: return
        self.parent[xRoot] = yRoot
        # 减少连通个数
        self.count -= 1

    def getCount(self):
        return self.count


class Solution02:
    def numIslands(self, grid: list) -> int:
        def getIndex(x, y, n):
            return x * n + y

        m, n = len(grid), len(grid[0])
        if m == 0: return 0
        spaces = 0
        uf = UnionFind(m * n)
        directions = [(1, 0), (0, 1)]
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '0':
                    spaces += 1
                else:
                    for direction in directions:
                        newX = i + direction[0]
                        newY = j + direction[1]
                        if newX < m and newY < n and grid[newX][newY] == '1':
                            curIdx = getIndex(i, j, n)
                            newIdx = getIndex(newX, newY, n)
                            uf.union(curIdx, newIdx)
        return uf.getCount() - spaces

if __name__ == '__main__':
    grid = [
        ["1", "1", "1", "1", "0"],
        ["1", "1", "0", "1", "0"],
        ["1", "1", "0", "0", "0"],
        ["0", "0", "0", "0", "0"]
    ]
    res = Solution02().numIslands(grid)
    print(res)